package bfsMaze;

import java.util.*;
public class Main {
    // 上、下、左、右 四个方向
    private static final int[] dx = {-1, 1, 0, 0};
    private static final int[] dy = {0, 0, -1, 1};
    private static final int SIZE = 10;
    /**
     * 计算从起点 'S' 到终点 'E' 的最短路径步数
     * @param maze 10x10 的迷宫字符数组
     * @return 最短步数，如果无法到达返回 -1
     */
    public static int shortestPathInMaze(char[][] maze) {
        if (maze == null || maze.length != SIZE || maze[0].length != SIZE) {
            return -1;
        }
        // 记录每个位置是否已访问
        boolean[][] visited = new boolean[SIZE][SIZE];
        // 队列：存储 (x, y, steps)，表示在 (x,y) 位置，走了 steps 步
        Queue<int[]> queue = new LinkedList<>();        
        // 寻找起点
        int startX = -1, startY = -1;
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (maze[i][j] == 'S') {
                    startX = i;
                    startY = j;
                    break;
                }
            }
            if (startX != -1) break;
        }
        // 从起点开始 BFS
        queue.offer(new int[]{startX, startY, 0});
        visited[startX][startY] = true;
        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];
            int steps = current[2];
            // 如果到达终点，返回步数
            if (maze[x][y] == 'E') {
                return steps;
            }
            // 向四个方向探索
            for (int i = 0; i < 4; i++) {
                int newX = x + dx[i];
                int newY = y + dy[i];
                // 检查边界、障碍物和是否已访问
                if (newX >= 0 && newX < SIZE && 
                    newY >= 0 && newY < SIZE && 
                    !visited[newX][newY] && 
                    maze[newX][newY] != '#') {                  
                    visited[newX][newY] = true;
                    queue.offer(new int[]{newX, newY, steps + 1});
                }
            }
        }
        // 队列为空仍未到达终点，说明无法到达
        return -1;
    }
    
    public static void main(String[] args) {
        // 示例 1：存在路径
        char[][] maze1 = {
            {'S', '.', '.', '#', '.', '.', '.', '.', '.', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '#', '#', '#', '#', '#', '.', '#', '.'},
            {'.', '.', '.', '.', '.', '.', '#', '.', '#', '.'},
            {'#', '#', '#', '#', '#', '.', '#', '.', '#', '.'},
            {'.', '.', '.', '.', '#', '.', '#', '.', '#', '.'},
            {'.', '#', '#', '.', '#', '.', '#', '.', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '#', '#', '#', '#', '#', '#', '#', '#', 'E'}
        };
        System.out.println("迷宫1 最短路径步数: " + shortestPathInMaze(maze1)); // 输出: 18 
        // 示例 2：无路径
        char[][] maze2 = {
            {'S', '#', '#', '#', '#', '#', '#', '#', '#', 'E'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '.', '.'},
            {'.', '#', '.', '#', '#', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '#', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '#', '#', '.', '#', '.'},
            {'.', '#', '.', '#', '.', '.', '.', '.', '#', '.'},
            {'.', '#', '.', '#', '#', '#', '#', '#', '#', '.'},
            {'.', '#', '.', '.', '.', '.', '.', '.', '#', '.'},
            {'.', '.', '.', '.', '#', '#', '#', '.', '.', '.'}
        };
        System.out.println("迷宫2 最短路径步数: " + shortestPathInMaze(maze2)); // 输出: 27
    }
}